package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         238,
		Discription: "除自身以外的数组乘积",
		Level:       2,
		Labels: map[string]int{
			"前缀和": 1,
		},
	})
}

func ProductExceptSelf(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	res[0] = 1
	//res[i]表示nums[:i]内的乘积
	for i := 1; i < n; i++ {
		res[i] = res[i-1] * nums[i-1]
	}

	//rightPlus表示nums[i+1:]的乘积反推过来
	//最终等于nums[:i]*nums[i+1:]
	rightPlus := 1
	for i := n - 2; i >= 0; i-- {
		rightPlus *= nums[i+1]
		res[i] *= rightPlus
	}

	return res
}
